#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
using namespace std;

//class Solution {
//public:
//    int maxArea(vector<int>& height) {
//        int left = 0, right = height.size() - 1;
//        int max = 0;
//        while (left < right)
//        {
//            int capacity = (right - left) *
//                (height[left] < height[right] ? height[left] : height[right]);
//
//            if (height[left] <= height[right])
//            {
//                left++;
//            }
//            else
//            {
//                right--;
//            }
//
//            if (capacity > max)
//            {
//                max = capacity;
//            }
//        }
//        return max;
//    }
//};


class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        sort(nums.begin(), nums.end());
        for (int end = n - 1; end > 1; --end)
        {
            int left = 0, right = end - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[end])
                {
                    count += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return count;
    }
};
